class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(-1);
        int res = 0, sz = heights.size();
        for(int i = 0; i < sz; ++i)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                int index = st.top();
                st.pop();
                int left = st.empty() ? -1 : st.top();
                res = max(res, (i - left - 1) * heights[index]);
            }
            st.push(i);
        }
        return res;
    }
};